#!/usr/bin/env python
#encoding latin1

from heap import *

class item_inventario:
	def __init__(self,identificador,valor,peso):
		self.identificador = identificador
		self.valor = valor
		self.peso = peso
		self.coef = valor / peso

class slot_mochila:
	def __init__(self,item,valor_acumulado):
		self.item = item
		self.valor_acumulado = valor_acumulado

def coef_comparar(a,b):
	if a.coef > b.coef:
		return 1
	elif a.coef < b.coef:
		return -1
	return 0

"""
Estas funciones resulven el problema de la mochila aplicando
distintos metodos de programacion.
"""
def resolver_mochila(inventario, carga_max, rapido = False):
	if rapido:
		resolver_mochila_greedy(inventario, carga_max)
	else:
		resolver_mochila_dinamica(inventario, carga_max)

def resolver_mochila_greedy(inventario, carga_max):
	heap_min = heap(coef_comparar)
	carga_libre = carga_max
	solucion = list()
	solucion.append(0)
	for i in inventario:
		heap_min.encolar(i)
	while carga_libre > 0 and heap_min.count > 0:
		item_a_evaluar = heap_min.desencolar()
		if item_a_evaluar.peso <= carga_libre:
			solucion.append(item_a_evaluar.identificador)
			solucion[0] += item_a_evaluar.valor
			carga_libre -= item_a_evaluar.peso
	return solucion

def resolver_mochila_dinamica(inventario, carga_max):
	solucion = list()
	matriz = list()
	maxfil = inventario.__len__() + 1
	maxcol = carga_max + 1
	for i in range(maxfil):
		vector = list()
		for j in range(maxcol):
			vector.append(slot_mochila(-1,0))
		matriz.append(vector)
	for fila in range(1,maxfil):
		for columna in range(1,maxcol):
			peso = inventario[fila-1].peso
			valor = inventario[fila-1].valor
			valor_anterior = matriz[fila-1][columna].valor_acumulado
			if peso > columna:
				matriz[fila][columna].valor_acumulado = valor_anterior
			else:
				valor_posible = matriz[fila - 1][columna - peso].valor_acumulado + valor
				if valor_anterior < valor_posible:
					matriz[fila][columna] = slot_mochila(inventario[fila-1].identificador, valor_posible)
				else:
					matriz[fila][columna].valor_acumulado = valor_anterior

	fila = maxfil - 1
	col = maxcol -1
	valor_total = matriz[fila][col].valor_acumulado
	while fila >= 0:
		item = matriz[fila][columna].item
		if item > -1:
			peso = inventario[fila-1].peso
			col -= peso
			solucion.append(item)
		fila -= 1
	solucion.reverse()
	solucion.insert(0,valor_total)
	return solucion
